package leetcode.l0615;

/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；
 * 否则，返回 false 。
 * @author Retain
 * @date 2021/6/15 18:39
 */
public class 经典Medium_单词搜索_79 {

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        exist(board,"ABCCED");
    }
    static boolean found = false;
    /**
     * 思路是使用回溯法，先找字母的开头字母，遇到了就进行dfs。
     * @param board
     * @param word
     * @return
     */
    public static boolean exist(char[][] board, String word) {
        if (board == null) {
            return false;
        }
        int m = board.length; int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        // 对每个格子进行遍历，然后回溯该格子的上下左右
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                backTrack(board,visited,0,word,i, j);
            }
        }
        return found;
    }

    /**
     *
     * @param board 棋盘
     * @param visited   visited数组
     * @param pos   该寻找的字符串索引，该索引之前都已经找到
     * @param word  字符串
     * @param i 当前格子i
     * @param j 当前格子j
     */
    public static void backTrack(char[][] board,boolean[][] visited, int pos,String word,int i,int j) {
        // 超出边界、已经访问过、字符跟单词的字母不匹配、已经找到，直接返回
        if (i<0 || i >= board.length ||j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !=word.charAt(pos) || found) {
            return;
        }
        //
        if (pos == word.length() - 1) {
            found = true;
            return;
        }
        // 修改已经访问过
        visited[i][j] = true;
        backTrack(board, visited,pos+1,word,i,j+1);
        backTrack(board, visited,pos+1,word,i+1,j);
        backTrack(board, visited,pos+1,word,i,j-1);
        backTrack(board, visited,pos+1,word,i-1,j);
        // 撤销
        visited[i][j] = false;
    }
}
